package com.study.yangfei.mystudy.activity;

import android.os.Bundle;
import android.support.design.widget.FloatingActionButton;
import android.support.design.widget.Snackbar;
import android.support.v7.app.AppCompatActivity;
import android.support.v7.widget.Toolbar;
import android.util.Log;
import android.view.View;

import com.study.yangfei.mystudy.R;

import java.util.ArrayList;

public class AlogStringDistanceActivity extends AppCompatActivity {

    int disCount = 0;
    @Override
    protected void onCreate(Bundle savedInstanceState) {
        super.onCreate(savedInstanceState);
        setContentView(R.layout.activity_string_distance);
        Toolbar toolbar = (Toolbar) findViewById(R.id.toolbar);
        setSupportActionBar(toolbar);

//        int len = stringDistance("snowy","sunny");
        String strSrc= "snowy";
        String strDst = "sunny";
        int len = stringDistanceEx(strSrc,strDst,0,0);
        Log.d("StringDistance","StringDistance = "+len + " disCount="+disCount);
    }

    public int stringDistance(String strA,String strB){
        Log.d("StringDistance","strA = "+strA + " strB="+strB+ " disCount="+disCount);
        disCount++;
        int strDis = 0;
        if(strA.length() == 0 || strB.length() == 0 ){
            return Math.abs(strA.length() - strB.length());
        }
        if(strA.charAt(0) == strB.charAt(0)){
            return stringDistance(strA.substring(1),strB.substring(1));
        }else{
            int ins = stringDistance(strA,strB.substring(1)) + 1;
            int del = stringDistance(strA.substring(1),strB) + 1;
            int rep = stringDistance(strA.substring(1),strB.substring(1)) + 1;

            strDis = Math.min(Math.min(ins,del),rep);
        }

        return strDis;
    }

    class tagMemoRecord{
        public int m;
        public int n;
        public int distance;
        public int refCount;

        public tagMemoRecord(int m,int n){
            this.m = m;
            this.n = n;
        }
    }

    ArrayList<tagMemoRecord> memo = new ArrayList<>();
    public int stringDistanceEx(String aStrA,String aStrB,int m,int n){
        Log.d("StringDistance","strA = "+aStrA + " strB="+aStrB+ " m="+m+ " n="+n+ " disCount="+disCount);
        disCount++;
        int strDis = 0;

        for(tagMemoRecord t:memo){
            if(t.m == m && t.n == n){
                t.refCount++;
                Log.d("StringDistance","strA = "+aStrA + " strB="+aStrB+ " m="+m+ " n="+n+ " refCount="+t.refCount);
                return t.distance;
            }
        }

        String strA = aStrA.substring(m);
        String strB = aStrB.substring(n);

        Log.d("StringDistance","strA = "+strA + " strB="+strB);

        if(strA.length() == 0 || strB.length() == 0 ){
            strDis =  Math.abs(strA.length() - strB.length());
        }else if(strA.charAt(0) == strB.charAt(0)){
            strDis =  stringDistanceEx(aStrA,aStrB,m+1,n+1);
        }else{
            int ins = stringDistanceEx(aStrA,aStrB,m,n+1) + 1;
            int del = stringDistanceEx(aStrA,aStrB,m+1,n) + 1;
            int rep = stringDistanceEx(aStrA,aStrB,m+1,n+1) + 1;

            strDis = Math.min(Math.min(ins,del),rep);
        }

        tagMemoRecord tr = new tagMemoRecord(m,n);
        tr.refCount++;
        tr.distance = strDis;

        memo.add(tr);
        return tr.distance;
    }
}
